package sort;

import java.util.Arrays;

//希尔排序
public class ShellSort {
    public static void main(String[] args) {
        int ary[] = new int[10];
        for (int i = 0; i < ary.length; i++) {
            int ran = (int) (Math.random() * 10);
            ary[i] = ran;
        }
        System.out.println(Arrays.toString(ary));
        System.out.println();

        /* //升序排序
        for (int gap = ary.length / 2; gap > 0; gap /= 2) {
            //从与增量值大小相等的下标开始，向右循环
            for (int i = gap; i < ary.length; i++) {
                //接下来的循环表示向左找“同组”的元素尝试对比及必要的换位
                //j：左侧“同组”元素的下标，即被对比元素的下标，因为可能有多个，所以需要循环
                for (int j = i - gap; j >= 0; j -= gap) {
                    //注意：使用的下标分别是j和j+gap，后者是因为j的值变化时需要跟随调整
                    if (ary[j] > ary[j + gap]) {
                        int temp = ary[j + gap];
                        ary[j + gap] = ary[j];
                        ary[j] = temp;
                        System.out.println(Arrays.toString(ary));
                    } else {
                        break;
                    }
                }
            }
            System.out.println();
        }*/

        //降序排序
        for (int gap = ary.length / 2 ; gap > 0; gap /=2) {
            for (int i = gap; i < ary.length; i++) {
                for (int j = i - gap; j >=0 ; j -= gap) {
                    if (ary[j+gap] > ary[j]){
                        int temp = ary[j];
                        ary[j] = ary[j+gap];
                        ary[j+gap] = temp;
                        System.out.println(Arrays.toString(ary));
                        System.out.println();
                    }
                }
            }
            System.out.println();
        }
    }
}
